package tulingxueyuan117;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/8 20:29
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 */
public class p43_二分查找_704 {
    public static void main(String[] args) {
        int[] arr = {1,3,5,15,17,87,98,95, 103};
        int target = 15;
        int res = search(arr, target);
        System.out.println(res);
    }
//    顺序查找，效果不好
//    public static int search(int[] nums, int target) {
//        int res = -1;
//        for(int i=0; i<nums.length; i++){
//            if(nums[i]==target){
//                res = i;
//            }
//        }
//        return res;
//    }

//    循环迭代
//    public static int search(int[] nums, int target) {
//        int start = 0, end = nums.length-1;
//        while (start <= end){
//            int mid = (start + end)/2;
//            if(nums[mid]<target)
//                start = mid+1;
//            else if(nums[mid]>target)
//                end = mid-1;
//            else return mid;
//        }
//        return -1;
//    }

//    递归
    public static int search(int[] nums, int target){
        return searchNum(nums, 0, nums.length-1, target);
    }
    public static int searchNum(int[] nums, int left, int right, int target){
        int mid = (left+right)/2;
        if(left<=right){
            if(nums[mid]<target)
                return searchNum(nums, mid+1,right,target);
            else if(nums[mid]>target)
                return searchNum(nums, left,  mid-1, target);
            else return mid;
        }
        return -1;
    }

}
